A digital signatures scheme is a method of authenticating digital information. The output of a digital signatures scheme is a binary string (or a pair of strings) that provides authenticity, integrity and non-repudiation of the transmitted message. A digital signatures scheme may be used to ensure that a message sent from a sender to a receiver is approved and authenticated, so that its content may be relied upon as not having been tampered with or having been generated by a source other than the sender.
Digital signatures algorithms (DSA) are based on public key cryptography (A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography. CRC Press, 1997) and consist of two parts: a signing algorithm and a verification algorithm.
Digital signatures algorithms, such as Lamport Signatures, Matyas-Meyer Signatures, RSA Signatures, ElGamal Signatures and others, are well-known and widely-used in practice (J. Pieprzyk, T. Hardjono, J. Sebbery, Fundamentals of Computer Security, Springer-Verlag, 2003).
NIST has published the Federal Information Processing Standard FIPS PUB 186, also known as the Digital Signature Standard (DSS). DSS uses SHA as the hashing algorithm together with a digital signatures algorithm (the “DSA”). DSA is based on the difficulty of computing the discrete logarithm problem as well as on the schemes presented by ELGamal and Shnorr (J. Pieprzyk, T. Hardjono, J. Sebbery, Fundamentals of Computer Security, Springer-Verlag, 2003).
Prior art digital signatures algorithms have been proven to be prone to attack. The potential that a digital signatures algorithm may be successfully attacked increases when an attacker is privy to the elements of the algorithm. In prior art digital signatures algorithms generally incorporate a public generator, as well as other public elements.